package com.kongge.algorithm.tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TreeNode<T> {
	public T value;
	public TreeNode<T> left;
	public TreeNode<T> right;
	
	public TreeNode(T value) {
		this.value = value;
	}
	
	public static <T> TreeNode<T> createTree(T[] values) {
		if (values == null || values.length == 0) {
			return null;
		}
		int index = 0;
		TreeNode<T> root = new TreeNode<T>(values[index]);
		createTreeNode(values, root, index);
		return root;
	}
	
	private static <T> void createTreeNode(T[] values, TreeNode<T> rootNode, int index) {
		if (rootNode == null) {
			return;
		}
		int leftIndex = index * 2 + 1;
		int rightIndex = index * 2 + 2;
		if (leftIndex < values.length) {
			rootNode.left = new TreeNode<T>(values[leftIndex]);
		}
		if (rightIndex < values.length) {
			rootNode.right = new TreeNode<T>(values[rightIndex]);
		}
		createTreeNode(values, rootNode.left, leftIndex);
		createTreeNode(values, rootNode.right, rightIndex);
	}
	
	public static <T> int getTreeDeep(TreeNode<T> root) {
		if (root == null) {
			return 0;
		}
		return getTreeDeep(root, 0);
	}
	
	public static <T> int getTreeDeep(TreeNode<T> root, int curDeep) {
		if (root == null) {
			return curDeep;
		}
		curDeep++;
		int leftDeep = getTreeDeep(root.left, curDeep);
		int rightDeep = getTreeDeep(root.right, curDeep);
		return Math.max(leftDeep, rightDeep);
	}
	
	/**
	 * 前序遍历
	 * @param rootNode
	 */
	public static <T> void preTraveseTree(TreeNode<T> rootNode, List<TreeNode<T>> resultList) {
		if (rootNode == null) {
			return;
		}
		if (resultList != null) {				
			resultList.add(rootNode);
		}
		preTraveseTree(rootNode.left, resultList);
		preTraveseTree(rootNode.right, resultList);
	}
	
	/**
	 * 中序遍历
	 * @param rootNode
	 * @param resultList
	 */
	public static <T> void middleTraveseTree(TreeNode<T> rootNode, List<TreeNode<T>> resultList) {
		if (rootNode == null) {
			return;
		}
		middleTraveseTree(rootNode.left, resultList);
		if (resultList != null) {				
			resultList.add(rootNode);
		}
		middleTraveseTree(rootNode.right, resultList);
	}
	
	/**
	 * 后序遍历
	 * @param rootNode
	 * @param resultList
	 */
	public static <T> void suffTraveseTree(TreeNode<T> rootNode, List<TreeNode<T>> resultList) {
		if (rootNode == null) {
			return;
		}
		suffTraveseTree(rootNode.left, resultList);
		suffTraveseTree(rootNode.right, resultList);
		if (resultList != null) {	
			resultList.add(rootNode);
		}
	}
	
	/**
	 * 层次遍历
	 * @param rootNode
	 * @param resultList
	 */
	public static <T> void arrangementTraveseTree(TreeNode<T> rootNode, List<TreeNode<T>> resultList) {
		if (rootNode == null) {
			return;
		}
		Queue<TreeNode<T>> treeNodeQueue = new LinkedList<TreeNode<T>>();
		treeNodeQueue.offer(rootNode);
		while (!treeNodeQueue.isEmpty()) {
			TreeNode<T> root = treeNodeQueue.poll();
			if (resultList != null) {				
				resultList.add(root);
			}
			if (root.left != null) {
				treeNodeQueue.offer(root.left);
			}
			if (root.right != null) {
				treeNodeQueue.offer(root.right);
			}
		}
	}
	
	public static <T> void printResult(List<TreeNode<T>> list) {
		if (list == null) {
			return;
		}
		for (TreeNode<T> treeNode : list) {
			System.out.print(treeNode.value + " ");
		}
	}
}
